package com.lsa.iview.lists;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

import junit.framework.TestCase;

import org.junit.Assert;

import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.lsa.helpers.IntegerComparator;
import com.lsa.iview.lists.SingeLinkedList.Node;

public class SingeLinkedListTest extends TestCase {
	public void testSimple() {
		SingeLinkedList<Integer> l = createSimpleList(1,2,3);
		Assert.assertEquals(Arrays.asList(1,2,3), Lists.newArrayList(l));
	}
	
	public void testCount() {
		SingeLinkedList<Integer> l = createSimpleList(5, 1,2,3,1,2,3,1,2,1,4);
		IntegerComparator c = IntegerComparator.instance();
		Assert.assertEquals(4, SingeLinkedListUtils.count(l, 1, c));
		Assert.assertEquals(3, SingeLinkedListUtils.count(l, 2, c));
		Assert.assertEquals(2, SingeLinkedListUtils.count(l, 3, c));
		Assert.assertEquals(1, SingeLinkedListUtils.count(l, 4, c));
		Assert.assertEquals(1, SingeLinkedListUtils.count(l, 5, c));
		Assert.assertEquals(0, SingeLinkedListUtils.count(l, 6, c));
	}
	
	public void testSize() {
		SingeLinkedList<Integer> l = createSimpleList(1,2,3);
		Assert.assertEquals(3, l.size());
		
		l = createSimpleList(1,2,3,4);
		Assert.assertEquals(4, l.size());
		
		l = createSimpleList();
		Assert.assertEquals(0, l.size());
		
		l = createSimpleList(1);
		Assert.assertEquals(1, l.size());
	}
	
	public void testGet() {
		SingeLinkedList<Integer> l = createSimpleList(1,2,3,4,5,6);
		Assert.assertEquals(6, l.size());
		for (int i = 0; i < l.size(); i++) {
			Assert.assertEquals((Object)(i+1), l.get(i).data);
		}
	}
	
	public void testClear() {
		SingeLinkedList<Integer> l = createSimpleList(1,2,3,4,5,6);
		l.clear();
		Assert.assertEquals(0, l.size());
	}
	
	public void testPop() {
		SingeLinkedList<Integer> l = createSimpleList(1,2,3,4,5,6);
		final int count = l.size();
		Assert.assertEquals(6, count);
		
		for (int i = 0; i < count; i++) {
			Node<Integer> n = l.pop();
			Assert.assertEquals((Object)(i+1), n.data);
		}
		
		Assert.assertEquals(0, l.size());
	}
	
	public void testInsertAt() {
		SingeLinkedList<Integer> l = createSimpleList(1,2,3);
		l.insert(0, 0);
		Assert.assertEquals(Arrays.asList(0,1,2,3), Lists.newArrayList(l));
		
		l = createSimpleList(1,2,3);
		l.insert(1, 0);
		Assert.assertEquals(Arrays.asList(1,0,2,3), Lists.newArrayList(l));
		
		l = createSimpleList(1,2,3);
		l.insert(2, 0);
		Assert.assertEquals(Arrays.asList(1,2,0,3), Lists.newArrayList(l));
		
		l = createSimpleList(1,2,3);
		l.insert(3, 0);
		Assert.assertEquals(Arrays.asList(1,2,3,0), Lists.newArrayList(l));
	}
	
	public void testSortedInsert() {
		IntegerComparator comparator = IntegerComparator.instance();
		
		SingeLinkedList<Integer> l = createSimpleList(10,20,30);
		l.sortedInsert(11, comparator);
		Assert.assertEquals(Arrays.asList(10, 11, 20,30), Lists.newArrayList(l));
		
		l = createSimpleList(10,20,30);
		l.sortedInsert(9, comparator);
		Assert.assertEquals(Arrays.asList(9, 10, 20,30), Lists.newArrayList(l));
		
		l = createSimpleList(10,20,30);
		l.sortedInsert(20, comparator);
		Assert.assertEquals(Arrays.asList(10, 20, 20,30), Lists.newArrayList(l));
		
		l = createSimpleList(10,20,30);
		l.sortedInsert(21, comparator);
		Assert.assertEquals(Arrays.asList(10, 20, 21,30), Lists.newArrayList(l));
		
		l = createSimpleList(10,20,30);
		l.sortedInsert(30, comparator);
		Assert.assertEquals(Arrays.asList(10, 20, 30, 30), Lists.newArrayList(l));
		
		l = createSimpleList(10,20,30);
		l.sortedInsert(32, comparator);
		Assert.assertEquals(Arrays.asList(10, 20, 30, 32), Lists.newArrayList(l));
		
		l = createSimpleList(10, 10, 10);
		l.sortedInsert(10, comparator);
		Assert.assertEquals(Arrays.asList(10, 10, 10, 10), Lists.newArrayList(l));
	}
	
	public void testInsertionSort() {
		IntegerComparator comparator = IntegerComparator.instance();
		
		SingeLinkedList<Integer> l = createSimpleList(10, 20, 30);
		l.insertionSort(comparator);
		Assert.assertEquals(Arrays.asList(10, 20, 30), Lists.newArrayList(l));
		
		l = createSimpleList(30, 20, 10);
		l.insertionSort(comparator);
		Assert.assertEquals(Arrays.asList(10, 20, 30), Lists.newArrayList(l));
		
		List<Integer> inputList = new ArrayList<>(Arrays.asList(5, 7, 4, 110, 88, 55, 11, 17)); 
		l = createSimpleList(inputList.toArray(new Integer[0]));
		l.insertionSort(comparator);
		Collections.sort(inputList);
		Assert.assertEquals(inputList, Lists.newArrayList(l));
		
		l = createSimpleList(1);
		l.insertionSort(comparator);
		Assert.assertEquals(Arrays.asList(1), Lists.newArrayList(l));
		
		l = createSimpleList();
		l.insertionSort(comparator);
		Assert.assertEquals(Arrays.asList(), Lists.newArrayList(l));
	}
	
	public void testAppend() {
		SingeLinkedList<Integer> l1 = createSimpleList(10, 20, 30);
		SingeLinkedList<Integer> l2 = createSimpleList(1, 2);
		testAppend(l1, l2);
		
		l1 = createSimpleList();
		l2 = createSimpleList();
		testAppend(l1, l2);
		
		l1 = createSimpleList(1);
		l2 = createSimpleList();
		testAppend(l1, l2);
		
		l1 = createSimpleList();
		l2 = createSimpleList(1,2);
		testAppend(l1, l2);
	}
	
	private void testAppend(SingeLinkedList<Integer> l1,
			SingeLinkedList<Integer> l2) {
		ArrayList<Integer> expected = Lists.newArrayList(Iterables.concat(l1, l2));
		l1.append(l2);
		Assert.assertEquals(expected, Lists.newArrayList(l1));
	}
	
	public void testFrontBackSplit() {
		SingeLinkedList<Integer> l1 = createSimpleList(10, 20, 30);
		testFrontBackSplit(l1);
		
		l1 = createSimpleList(10, 20, 30, 40);
		testFrontBackSplit(l1);
		
		l1 = createSimpleList(10, 20, 30, 40, 50);
		testFrontBackSplit(l1);
		
		l1 = createSimpleList(10, 20, 30, 40, 50, 60);
		testFrontBackSplit(l1);
		
		l1 = createSimpleList(10, 20);
		testFrontBackSplit(l1);
		
		l1 = createSimpleList(10);
		List<SingeLinkedList<Integer>> parts = l1.frontBackSplit();
		Assert.assertEquals(Arrays.asList(10), Lists.newArrayList(parts.get(0)));
		Assert.assertEquals(Arrays.asList(), Lists.newArrayList(parts.get(1)));
		
		l1 = createSimpleList();
		parts = l1.frontBackSplit();
		Assert.assertEquals(Arrays.asList(), Lists.newArrayList(parts.get(0)));
		Assert.assertEquals(Arrays.asList(), Lists.newArrayList(parts.get(1)));
	}
	
	private void testFrontBackSplit(SingeLinkedList<Integer> l1) {
		List<Integer> test = Lists.newArrayList(l1);
		List<SingeLinkedList<Integer>> parts = l1.frontBackSplit();
		
		List<Integer> leftSublist = test.subList(0, (int) Math.ceil(test.size() / 2.0) );
		Assert.assertEquals(leftSublist, Lists.newArrayList(parts.get(0)));
		
		List<Integer> rightSublist = test.subList((int) Math.ceil(test.size() / 2.0), test.size());
		Assert.assertEquals(rightSublist, Lists.newArrayList(parts.get(1)));
	}

	public void testReverse() {
		List<Integer> input = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50, 60));
		testReverse(input);
		
		input = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50));
		testReverse(input);
		
		input = new ArrayList<>(Arrays.asList(10, 20, 40, 30));
		testReverse(input);
		
		input = new ArrayList<>(Arrays.asList(10, 20));
		testReverse(input);
		
		input = new ArrayList<>(Arrays.asList(10));
		testReverse(input);
		
		input = new ArrayList<>();
		testReverse(input);
	}

	private void testReverse(List<Integer> input) {
		SingeLinkedList<Integer> l = createSimpleList(input.toArray(new Integer[0]));
		Collections.reverse(input);
		l.reverse();
		Assert.assertEquals(input, Lists.newArrayList(l));
	}
	
	public void testRecursiveReverse() {
		List<Integer> input = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50, 60));
		testRecursiveReverse(input);
		
		input = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50));
		testRecursiveReverse(input);
		
		input = new ArrayList<>(Arrays.asList(10, 20, 40, 30));
		testRecursiveReverse(input);
		
		input = new ArrayList<>(Arrays.asList(10, 20));
		testRecursiveReverse(input);
		
		input = new ArrayList<>(Arrays.asList(10));
		testRecursiveReverse(input);
		
		input = new ArrayList<>();
		testRecursiveReverse(input);
	}
	
	private void testRecursiveReverse(List<Integer> input) {
		SingeLinkedList<Integer> l = createSimpleList(input.toArray(new Integer[0]));
		Collections.reverse(input);
		l.recursiveReverse();
		Assert.assertEquals(input, Lists.newArrayList(l));
	}

	public void testRemoveDuplicates() {
		List<Integer> input = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50, 60));
		SingeLinkedList<Integer> l = createSimpleList(input.toArray(new Integer[0]));
		l.removeDuplicates(IntegerComparator.instance());
		Assert.assertEquals(input, Lists.newArrayList(l));
		
		input = new ArrayList<>(Arrays.asList(10, 20, 30, 40, 50, 50, 60));
		l = createSimpleList(input.toArray(new Integer[0]));
		l.removeDuplicates(IntegerComparator.instance());
		Assert.assertEquals(Arrays.asList(10, 20, 30, 40, 50, 60), Lists.newArrayList(l));
		
		input = new ArrayList<>(Arrays.asList(10, 10, 30, 40, 50, 50, 60));
		l = createSimpleList(input.toArray(new Integer[0]));
		l.removeDuplicates(IntegerComparator.instance());
		Assert.assertEquals(Arrays.asList(10, 30, 40, 50, 60), Lists.newArrayList(l));
		
		input = new ArrayList<>(Arrays.asList(10, 10, 10, 20, 20, 30, 30, 40, 40,  50, 50, 60, 60));
		l = createSimpleList(input.toArray(new Integer[0]));
		l.removeDuplicates(IntegerComparator.instance());
		Assert.assertEquals(Arrays.asList(10, 20, 30, 40, 50, 60), Lists.newArrayList(l));
		
		input = new ArrayList<>();
		for (int i = 0; i < 10000; i++) {
			input.add(0);
		}
		l = createSimpleList(input.toArray(new Integer[0]));
		l.removeDuplicates(IntegerComparator.instance());
		Assert.assertEquals(Arrays.asList(input.get(0)), Lists.newArrayList(l));
		
		input = new ArrayList<>();
		input.add(0);
		l = createSimpleList(input.toArray(new Integer[0]));
		l.removeDuplicates(IntegerComparator.instance());
		Assert.assertEquals(Arrays.asList(input.get(0)), Lists.newArrayList(l));
		
		input = new ArrayList<>();
		l = createSimpleList(input.toArray(new Integer[0]));
		l.removeDuplicates(IntegerComparator.instance());
		Assert.assertEquals(Arrays.asList(), Lists.newArrayList(l));
	}
	
	public void testTransplantHead() {
		SingeLinkedList<Integer> l1 = createSimpleList(10, 20, 30, 40);
		SingeLinkedList<Integer> l2 = createSimpleList(101, 201, 301, 401);
		l1.transplantHead(l2);
		
		Assert.assertEquals(Arrays.asList(101, 10, 20, 30, 40), Lists.newArrayList(l1));
		Assert.assertEquals(Arrays.asList(201, 301, 401), Lists.newArrayList(l2));
	}
	
	public void testOddEventElementsSplit() {
		LinkedList<Integer> l = new LinkedList<>(Arrays.asList(10, 20, 30, 40, 50, 60)); 
		while(!l.isEmpty()) {
			testOddEventElementsSplit(l);
			l.pop();
		}
		
		testOddEventElementsSplit(l);
	}
	
	public void testShuffleMerge() {
		testShuffleMerge(Arrays.asList(10, 20, 30, 40), Arrays.asList(10, 20, 30, 40));
		testShuffleMerge(Arrays.asList(10), Arrays.asList(10, 20, 30, 40));
		testShuffleMerge(new ArrayList<Integer>(), Arrays.asList(10, 20, 30, 40));
		testShuffleMerge(Arrays.asList(10, 20, 30, 40), new ArrayList<Integer>());
		testShuffleMerge(new ArrayList<Integer>(), new ArrayList<Integer>());
		testShuffleMerge(Arrays.asList(10, 20, 30, 40), Arrays.asList(1, 2));
	}

	private void testShuffleMerge(List<Integer> tl1, List<Integer> tl2) {
		SingeLinkedList<Integer> l1 = createSimpleList(tl1.toArray(new Integer[0]));
		SingeLinkedList<Integer> l2 = createSimpleList(tl2.toArray(new Integer[0]));
	
		Assert.assertEquals(shuffleMerge(tl1, tl2), Lists.newArrayList(SingeLinkedListUtils.shuffleMerge(l1, l2)));
	}
	
	public void testMerge() {
		testMerge(Arrays.asList(11, 21, 31, 41), Arrays.asList(2, 2, 3, 4, 6, 8));
		testMerge(Arrays.asList(1, 2, 3, 4), Arrays.asList(2, 2, 3, 4, 6, 8, 11, 18));
		testMerge(Arrays.asList(1, 2, 3), Arrays.asList(2, 2, 3, 4, 6, 11, 18));
		testMerge(Arrays.asList(1, 2, 3, 4,8,11,17), Arrays.asList(2, 2, 3, 4, 6, 8));
		testMerge(Arrays.asList(1, 2, 3, 4), Arrays.asList(21, 22, 31, 41, 61, 81));
	}

	private void testMerge(List<Integer> tl1, List<Integer> tl2) {
		SingeLinkedList<Integer> l1 = createSimpleList(tl1.toArray(new Integer[0]));
		SingeLinkedList<Integer> l2 = createSimpleList(tl2.toArray(new Integer[0]));
		
		SingeLinkedList<Integer> r = SingeLinkedListUtils.merge(l1, l2, IntegerComparator.instance());
		Assert.assertEquals(merge(tl1, tl2),
				Lists.newArrayList(r));
	}
	
	private List<Integer> merge(List<Integer> tl1, List<Integer> tl2) {
		List<Integer> r = new ArrayList<>();
		r.addAll(tl1);
		r.addAll(tl2);
		Collections.sort(r);
		return r;
	}
	
	public void testMergeSort() {
		testMergeSort(Arrays.asList(2,1,4,3,6,5,8,7,10,9));
		testMergeSort(Arrays.asList(1));
		testMergeSort(Arrays.asList(1,2));
		testMergeSort(Arrays.asList(1,2,3));
		testMergeSort(Arrays.asList(3,2,1));
		testMergeSort(Arrays.asList(3,23,1));
	}

	private void testMergeSort(List<Integer> lt) {
		SingeLinkedList<Integer> l = createSimpleList(lt.toArray(new Integer[0]));
		l = SingeLinkedListUtils.mergeSort(l, IntegerComparator.instance());
		
		Collections.sort(lt);
		Assert.assertEquals(lt, Lists.newArrayList(l));
	}
	
	public static void testSortedIntersect() {
		testSortedIntersect(Arrays.asList(1, 2, 3, 4), Arrays.asList(2, 2, 3, 4, 6, 8, 11, 18));
		testSortedIntersect(Arrays.asList(1, 1, 1, 1), Arrays.asList(1, 1, 1));
		testSortedIntersect(Arrays.asList(1, 4, 5, 6, 11), Arrays.asList(2, 3, 4, 5, 6, 7, 8, 9, 10));
		testSortedIntersect(Arrays.asList(1, 4, 5, 6, 11), Arrays.asList(2, 3));
		testSortedIntersect(Arrays.asList(2, 2), Arrays.asList(2, 2, 3, 4, 6, 8, 11, 18));
		testSortedIntersect(Arrays.asList(11, 18), Arrays.asList(2, 2, 3, 4, 6, 8, 11, 18));
	}

	private static void testSortedIntersect(List<Integer> tl1, List<Integer> tl2) {
		List<Integer> tr = sortedIntersect(tl1, tl2, IntegerComparator.instance());
		
		SingeLinkedList<Integer> l1 = createSimpleList(tl1.toArray(new Integer[0]));
		SingeLinkedList<Integer> l2 = createSimpleList(tl2.toArray(new Integer[0]));
		
		SingeLinkedList<Integer> r = SingeLinkedListUtils.sortedIntersect(l1, l2, IntegerComparator.instance());
		Assert.assertEquals(tr, Lists.newArrayList(r));
		Assert.assertEquals(tl1, Lists.newArrayList(l1));
		Assert.assertEquals(tl2, Lists.newArrayList(l2));
	}
	
	private static <E> List<E> sortedIntersect(List<E> tl1, List<E> tl2, Comparator<E> c) {
		List<E> r = new ArrayList<>();

		if (tl1.isEmpty() || tl2.isEmpty()) {
			return r;
		}
		
		int i = 0, j = 0;
		
		while(i != tl1.size() && j != tl2.size()) {
			int cmp = c.compare(tl1.get(i), tl2.get(j));
			if (cmp < 0){
				i++;
			}
			else if (cmp > 0){
				j++;
			}
			else {
				r.add(tl1.get(i));
				i++;
				j++;
			}
		}
		
		return r;
	}
	
	public static List<Integer> shuffleMerge(List<Integer> l1, List<Integer> l2) {
		List<Integer> r = new ArrayList<>();
		
		int i = 0, j = 0;
		int selector = !l1.isEmpty()? 0 : 1;
		while( i != l1.size() || j != l2.size()) {
			if (i != l1.size() && selector == 0) {
				r.add(l1.get(i++));
			}
			
			if (j != l2.size() && selector == 1) {
				r.add(l2.get(j++));
			}
			
			selector = (selector + 1) % 2;
		}
		
		return r;
	}

	private void testOddEventElementsSplit(List<Integer> input) {
		SingeLinkedList<Integer> l = createSimpleList(input.toArray(new Integer[0]));
		
		List<SingeLinkedList<Integer>> split = l.oddEventElementsSplit();
		List<List<Integer>> testSplit = oddEventElementsSplit(input);
		
		for (int i = 0; i < 2; i++) {
			Assert.assertEquals(testSplit.get(i), Lists.newArrayList(split.get(i)));
		}
	}
	
	private List<List<Integer>> oddEventElementsSplit(List<Integer> l) {
		LinkedList<Integer> oddList = new LinkedList<>();
		LinkedList<Integer> evenList = new LinkedList<>();
		for (int i = 0; i < l.size(); i++) {
			if (i % 2 == 0) {
				oddList.addFirst(l.get(i));
			}
			else {
				evenList.addFirst(l.get(i));
			}
		}
		
		return Arrays.asList((List<Integer>)oddList, (List<Integer>)evenList);
	}
	
	public static void testAppendNMinusOneElementsInReverseOrder() {
		testAppendNMinusOneElementsInReverseOrder(1);
		testAppendNMinusOneElementsInReverseOrder(1,2);
		testAppendNMinusOneElementsInReverseOrder(1,2,3);
		testAppendNMinusOneElementsInReverseOrder(1,2,3,4);
		testAppendNMinusOneElementsInReverseOrder(1,2,3,4,5);
	}

	private static void testAppendNMinusOneElementsInReverseOrder(Integer... arr) {
		SingeLinkedList<Integer> l = createSimpleList(arr);
		SingeLinkedListUtils.appendNMinusOneElementsInReverseOrder(l);
		Assert.assertEquals(Arrays.asList(appendnMinusOneElementsInReverseOrder(arr)), Lists.newArrayList(l));
	}
	
	public static Integer[] appendnMinusOneElementsInReverseOrder(Integer[] arr) {
		Integer[] newArr = new Integer[2*arr.length - 1];
		for (int i = 0; i < arr.length - 1; i++) {
			newArr[i] = arr[i];
			newArr[newArr.length - 1 - i] = arr[i];
		}
		newArr[arr.length - 1] = arr[arr.length - 1];
		return newArr;
	}
	
	private static <E> SingeLinkedList<E> createSimpleList(E... elements ) {
		SingeLinkedList<E> l = new SingeLinkedList<E>();
		if (elements.length == 0) {
			return l; 
		}
		Node<E> tail = l.add(elements[0]);
		for (int i = 1; i < elements.length; i++) {
			tail = SingeLinkedList.insertAfter(tail, elements[i]);
		}
		return l;
	}
}
